package middle;

/**
 * 请你判断一个9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 *
 * 数字1-9在每一行只能出现一次。
 * 数字1-9在每一列只能出现一次。
 * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
 * 
 *
 * 注意：
 *
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 空白格用'.'表示
 *
 * 链接：https://leetcode.cn/problems/valid-sudoku
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class ValidSudoku {
    /**
     * 复杂的问题简单化
     * 我们可以先试想一下只有前两种规则的时候，这道题你会怎么做。
     * 我会定义两个二维数组，一个数组用来记录每一行中数字1-9出现的次数，
     * 如row[0][0]表示第1行数字1出现的次数，所以这个二维数组的大小就是9*9的
     *
     * 搞定了行和列，我们再来看第3条规则。通过观察我们发现，任意一个格子，其横坐标/3， 纵坐标/3
     * 就可以得出来其所在的九宫格。所以我们需要定义一个三维数组，前面两个维度是坐标，后面是对应数字出现的次数
     *
     * 当然，我们没有3维数组，所以只能够从3维转为2维。我们将九宫格化成9个格子，位于（0,0）位置的格子，就是第1个格子
     * 位于（1,1）的格子就是第五个格子，如何算出来的呢？
     * 第一个数字是行，第1行对应的是实际的第2行，那么1行的数量是3个格子。这个格子至少是第3个格子
     * 第二个数字是列，代表这行开始的第几个，1就是第二个格子，那么最后算得就是1 * 3 + 2 = 5
     * */
    class Solution {
        public boolean isValidSudoku(char[][] board) {
            int[][] row = new int[9][9];
            int[][] col = new int[9][9];
            int[][] pos = new int[9][9];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if(board[i][j] == '.'){
                        continue;
                    }
                    if(row[i][board[i][j] - '1'] == 1){
                        return false;
                    }
                    row[i][board[i][j] - '1']++;
                    if(col[j][board[i][j] - '1'] == 1){
                        return false;
                    }
                    col[j][board[i][j] - '1']++;
                    int[] po = pos[3 * (i / 3) + j / 3];
                    if(po[board[i][j] - '1'] == 1){
                        return false;
                    }
                    po[board[i][j] - '1']++;
                }
            }
            return true;
        }
    }
}
